package com.maozzi.dp;

import java.util.Arrays;

/**
 * 分割等和子集
 * <p>
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * 示例 1：
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
 * 示例 2：
 * 输入：nums = [1,2,3,5]
 * 输出：false
 * 解释：数组不能分割成两个元素和相等的子集。
 *
 * @author maozi
 */
public class Subset {

    public static void main(String[] args) {
        int[] arr1 = {1, 5, 11, 5};
        int[] arr2 = {3, 3, 3, 4, 5};
        System.out.println(canPartition(arr1));
        System.out.println(canPartition(arr2));

        System.out.println(canPartitionDp(arr1));
        System.out.println(canPartitionDp(arr2));
        System.out.println(canPartitionDp1D(arr2));

        System.out.println(findTargetSumWays(arr1, 10));

        System.out.println(lastStoneWeight(arr1));

        System.out.println(findMaxForm(new String[]{"10", "0001", "111001", "1", "0"}, 4, 3));
    }

    /**
     * 回溯算法
     */
    public static boolean canPartition(int[] nums) {
        return f(nums, 0, 0, 0);
    }

    public static boolean f(int[] arr, int i, int l, int r) {
        if (i == arr.length - 1 && l == r) {
            return true;
        }
        if (i < arr.length - 1) {
            int temp = arr[i];
            if (temp != -1) {
                arr[i] = -1;
                if (f(arr, i + 1, l + temp, r)) {
                    return true;
                } else {
                    if (f(arr, i + 1, l + temp, r)
                            || f(arr, i + 1, l, r + temp)) {
                        return true;
                    }
                }
            }
            arr[i] = temp;
        }
        return false;
    }

    /**
     * 动态规划解法
     */
    public static boolean canPartitionDp(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum /= 2;
        System.out.println(sum);
        int[][] dp = new int[nums.length][sum + 1];
        for (int i = 0; i <= sum; i++) {
            dp[0][i] = nums[0];
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= sum; j++) {
                if (j >= nums[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(Arrays.deepToString(dp));
        return dp[nums.length - 1][sum] == sum;
    }

    public static boolean canPartitionDp1D(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum /= 2;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int i = 1; i < nums.length; i++) {
            for (int j = sum; j >= nums[i]; j--) {
                dp[j] |= dp[j - nums[i]];
            }
        }
        return dp[sum];
    }

    /**
     * 最后一块石头的重量II
     * <p>
     * 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
     * <p>
     * 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
     * <p>
     * 如果 x == y，那么两块石头都会被完全粉碎；
     * 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
     * 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
     */
    public static int lastStoneWeight(int[] stones) {
        int sum = 0;
        for (int num : stones) {
            sum += num;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for (int stone : stones) {
            for (int j = target; j >= stone; j--) {
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
            }
        }
        return sum - 2 * dp[target];
    }

    /**
     * 目标和
     * <p>
     * 给你一个非负整数数组 nums 和一个整数 target 。
     * <p>
     * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
     * <p>
     * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
     * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
     */
    public static int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        int temp = sum + target;
        if (temp % 2 == 1 || Math.abs(target) > sum) {
            return 0;
        }
        int capacity = (sum + target) / 2;
        int[] dp = new int[capacity + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = capacity; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[capacity];
    }

    /**
     * 一和零
     * <p>
     * 给你一个二进制字符串数组 arr 和两个整数 m 和 n 。
     * <p>
     * 请你找出并返回 arr 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
     * <p>
     * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
     */
    public static int findMaxForm(String[] arr, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String s : arr) {
            int zeroNum = s.replaceAll("1", "").length();
            int oneNum = s.replaceAll("0", "").length();
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}